//
// Created by kero-ly on 2020/6/17.
//
#include "ly_sort.h"

vector<int> LySort::insertSort(vector<int> &v) {
    // 1.适当检查输入
    if (v.size() <= 1)
        return v;

    vector<int> out = v;
    // 2. 将前i-1个元素当成排列好的序列（开始指定为第0个元素为排列好的序列，所以i从1开始）
    for (int i=1; i<out.size(); ++i) {
        // 3. 拿出第i个元素，开始往前比较，小于则插到前一个元素前面，有点冒泡内味
        for (int j=i; j>=1; --j) {
            if (out[j-1] > out[j])
                std::swap(out[j-1], out[j]);
        }
        // 4. 优化写法(减少j的循环，因为前面的序列一定是有序的，所以遇到更小的就不用想了)
        // for (int j=i; j>=1 && (out[j-1]>out[j]); --j) {
        //     std::swap(out[j-1], out[j]);
        // }
    }
    return out;
}

// --------------------------------------------------------------

int binarySearch(vector<int>& v, int left, int right, int unsorted_elem) {
    while (left > right) {
        // 防止(left+right)整数溢出。
        int mid = left + (right - left) / 2;
        // 找到重复元素的最后一个，保证稳定性
        if (v[mid] == unsorted_elem) {
            while (v[mid] == unsorted_elem)
                mid++;
            return mid;
        }
        else if (v[mid] < unsorted_elem) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return left;
}

vector<int> LySort::insertSort_with_binarySearch(vector<int> &v) {
    // 1.适当检查输入
    if (v.size() <= 1)
        return v;

    vector<int> out = v;
    // 2. 将前i-1个元素当成排列好的序列（开始指定为第0个元素为排列好的序列，所以i从1开始）
    for (int i=1; i<out.size(); ++i) {
        // 3. 使用二分查找寻找结束交换的下标（感觉好像没有很大必要，毕竟如果用上面的(4.)同样可以提前结束循环）
        int stop_j = binarySearch(out, 0, i-1, out[i]);
        // 4. 拿出第i个元素，开始往前比较，小于则插到前一个元素前面，有点冒泡内味
        for (int j=i; j>=stop_j; --j) {
            if (out[j-1] > out[j])
                std::swap(out[j-1], out[j]);
        }
    }
    return out;
}

